Câu lạc bộ bóng đá Valenciennes được thành lập vào năm 1913 bởi một nhóm thanh niên được biết đến là Colson, Joly và Bouly. Do câu lạc bộ có nguồn lực hạn chế và sự hình thành của nó trùng với sự khởi đầu của Thế chiến I, Valenciennes đã tìm cách hợp nhất giữa các câu lạc bộ địa phương trong thành phố. Việc sáp nhập được hoàn thành vào năm 1916 và câu lạc bộ đổi tên thành Union Sportive de Valenciennes Anzin (USVA) trong quá trình này. Sau khi sáp nhập, câu lạc bộ mới đã dành 15 năm sau đó để chơi Giải vô địch quận de deEscaut. Vào tháng 7 năm 1930, Hội đồng Quốc gia Liên đoàn bóng đá Pháp đã bầu tỷ lệ phiếu 128-20 để ủng hộ sự chuyên nghiệp trong bóng đá Pháp. Valenciennes, dưới sự lãnh đạo của chủ tịch M. Le Mithouard, đã đạt được sự chuyên nghiệp vào năm 1933 và được đưa vào Division 2. Câu lạc bộ, sau đó, đã trở thành thành viên sáng lập của bộ phận thứ hai của bóng đá Pháp.

Trong mùa khai mạc của Division 2, Valenciennes kết thúc ở vị trí thứ 7 trong nhóm. Trong mùa giải tiếp theo, bảng đấu đã được chuyển đổi thành một bảng duy nhất và kết quả là Valenciennes ở vị trí thứ 2 giành được suất thăng hạng lên Division 1. Trong giai đoạn này, câu lạc bộ đáng chú ý được dẫn dắt bởi các cầu thủ nước ngoài như người Anh Peter O'Dowd và George Gibson và những tiền đạo gốc Đức Édouard Waggi và Ignace Kowalczyk. Trong mùa giải đầu tiên của câu lạc bộ ở Division 1, Valenciennes đã hoàn thành vị trí thứ 15 rơi trở lại Division 2. Câu lạc bộ đã hoàn thành ngang nhau về số điểm với Red Star Olympique, nhưng do có ít chiến thắng hơn và hiệu số bàn thắng ít hơn, Valenciennes đã xuống hạng. Sau khi bị xuống hạng, câu lạc bộ đã mang đến một vị chủ tịch mới - Turbot. Ngay sau khi đến, Turbot đã cho ra mắt một số cầu thủ quốc tế của câu lạc bộ và mang theo những người như Ernest Libérati để thay thế họ. Quá trình chuyển đổi là một thành công với việc câu lạc bộ kiếm được suất thăng hạng trở lại Division 1 vào năm 1937. Tuy nhiên, Valenciennes trở lại trong Division 1 tương đương với lần đầu tiên. Câu lạc bộ kết thúc ở vị trí cuối cùng trong mùa giải 1937-38 và xuống hạng 2. Do Chiến tranh thế giới thứ hai, Valenciennes trở lại trạng thái nghiệp dư và trải qua ba trong sáu mùa giải chơi bóng đá nghiệp dư thời chiến.

Sau chiến tranh, Valenciennes trở lại thi đấu chuyên nghiệp một lần nữa và trở lại trong Division 2. Câu lạc bộ đã dành một thập kỷ ở Division 2 trước khi được thăng hạng Division 1 trước mùa giải 1956. Dưới thời huấn luyện viên Charles Demeillez, năm 1951, Valenciennes lọt vào trận chung kết Coupe de France. Trong trận chung kết, câu lạc bộ phải đối mặt với Strasbourg và bị hạ bệ 3-0 tại Stade Olympique Yves-du-Manoir ở Colombes. Trong câu lạc bộ trở lại Division 1, Valenciennes kết thúc ở nửa sau của bảng trong ba mùa liên tiếp. Vào năm 1959, Valenciennes lọt vào trận chung kết của Coupe Drago, nhưng bị Lens đánh bại 3-2 trong hiệp phụ của trận đấu tại sân vận động Parc des Princes. Trong mùa giải 1959-60, Valenciennes có thành tích kết thúc tốt nhất ở giải hạng 1 sau khi đứng thứ 8 trên BXH. Tuy nhiên, huấn luyện viên Robert Domergue đã không thể giữ được sự nhất quán khi Valenciennes kết thúc thứ 19 trong mùa giải tiếp theo. Valenciennes, hiện đang được dẫn dắt bởi các cầu thủ trẻ Bolec Kocik và Serge Masnaghetti, đã thăng hạng trở lại Division 1 sau một mùa giải và trải qua chín năm chơi ở Division 1. Trong thời gian hoạt động, Domergue đã dẫn dắt câu lạc bộ đạt thành tích cao nhất từ trước đến nay trong giải hạng nhất khi câu lạc bộ kết thúc thứ 3 trong các mùa giải trở lại vào năm 1965 và 1966. Sau mùa giải 1966, Domergue rời câu lạc bộ và anh được thay thế bởi Gaby Robert. Cả Robert và người kế nhiệm Louis Provelli đều không thể phù hợp với sự nhất quán của Domergue và ông trở lại câu lạc bộ vào năm 1970. Trong mùa giải đầu tiên của câu lạc bộ, Domergue đã dẫn dắt câu lạc bộ xuống hạng năm 1971, đưa câu lạc bộ trở lại Division 1 vào năm 1972, và huấn luyện câu lạc bộ để xuống hạng một lần nữa vào năm 1973. Anh ra đi sau mùa giải và được thay thế bởi Jean-Pierre Destrumelle.

Sau khi trải qua những năm đầu thập niên 1970 lơ lửng giữa Division 1 và Division 2, Destrumelle đã dẫn dắt câu lạc bộ trở lại Division 1 cho mùa giải 1975-76. Huấn luyện viên có phần lớn tài năng trong câu lạc bộ, nổi bật nhất là Bruno Metsu, Bruno Zaremba, Dominique Dropsy, và Didier Six và giữ câu lạc bộ trụ hạng trong Division 1 cho toàn bộ mùa giải, tuy nhiên, sau khi kết thúc ở vị trí thứ 18 năm 1979, Dustremelle đã bị sa thải và được thay thế bằng sự kết hợp của Erwin Wilczek và Bolek Tomowski. Dưới bộ đôi này, Valenciennes tồn tại ở Division 1 cho đến mùa giải 1983. Câu lạc bộ, sau đó, đã dành thập kỷ tiếp theo để chơi ở Division 2 dưới năm huấn luyện viên khác nhau, khiến những người ủng hộ dần dần trở nên tách rời với câu lạc bộ.

Từ năm 1988-1991, Valenciennes đã cải thiện đáng kể dưới thời huấn luyện viên Georges Peyroche. Peyroche rời câu lạc bộ vào năm 1991 và Francis Smerecki được chỉ định làm người thay thế. Trong mùa giải đầu tiên của Smerecki, ông đã dẫn dắt câu lạc bộ trở lại Division 1. Trong mùa giải đầu tiên của câu lạc bộ trở lại, Valenciennes đã dính vào một vụ bê bối hối lộ làm mất hiệu quả câu lạc bộ trong thập kỷ tiếp theo. Các vụ bê bối, trong đó liên quan đến Marseille tiền vệ Jean-Jacques Eydelie và tổng giám đốc của câu lạc bộ dưới quyền Chủ tịch câu lạc bộ Bernard Tapie hối lộ cầu thủ Valenciennes Christophe Robert, Jacques Glassmann, và Jorge Burruchaga, đã trở thành tiêu đề tin tức chủ yếu là do Marseille là câu lạc bộ nổi tiếng nhất trong Quốc gia. Người ta đã khẳng định rằng tiền hối lộ được thực hiện để các cầu thủ Valenciennes "dễ dàng" với các cầu thủ của Marseille với câu lạc bộ sau đó phải chơi trong trận Chung kết UEFA Champions League năm 1993 với câu lạc bộ Milan của Ý chỉ vài ngày sau đó. Marseille đánh bại Valenciennes 1-0 và tiếp tục đánh bại Milan để trở thành câu lạc bộ đầu tiên của Pháp giành chiến thắng trong giải đấu cấp châu Âu. Sau khi âm mưu bị phát hiện, Robert thừa nhận đã nhận hối lộ, Burruchaga thừa nhận ban đầu đồng ý với nó, nhưng sau đó đã đổi ý, trong khi Glassmann nói rằng ông không bao giờ đồng ý với thỏa thuận này.[3] Các báo cáo sau đó về vụ bê bối đã hoàn toàn làm mờ hình ảnh của Valenciennes và một số cầu thủ rời câu lạc bộ trong bối cảnh bối rối và suy đoán rằng họ cũng tham gia vào âm mưu này. Với câu lạc bộ hiện đang chơi ở Ligue 2, Valenciennes đã không thể đối phó với thiệt hại thấm nhuần do vụ bê bối và kết thúc vị trí cuối cùng trong giải đấu, do đó rơi xuống giải hạng ba lần đầu tiên trong những năm tồn tại của câu lạc bộ. Hai mùa sau, câu lạc bộ đã xuống hạng thứ tư do vấn đề tài chính. Trước mùa giải 1996-97, câu lạc bộ rơi vào tình trạng nghiệp dư sau khi nộp đơn xin phá sản.

Vào ngày 1 tháng 4 năm 1996, câu lạc bộ được đổi tên thành Câu lạc bộ bóng đá Valenciennes và kết thúc ở vị trí thứ năm trong mùa giải khai mạc dưới tên mới. Trong mùa giải tiếp theo, bộ phận thứ tư được đổi tên thành Championnat de France amateur và Valenciennes trở thành nhà vô địch khai mạc của giải đấu. Trong bảy mùa giải tiếp theo, Valenciennes đã chơi ở Championnat National, ngoại trừ một mùa trở lại trong CFA. Trong mùa giải 2004-05, câu lạc bộ đã giành chiến thắng tại National và trở lại giải hạng hai, bây giờ được gọi là Ligue 2. Đáng ngạc nhiên, sau một mùa giải, Valenciennes được thăng hạng trở lại giải đấu cao nhất, bây giờ được gọi là Ligue 1, dưới sự lãnh đạo của Antoine Kombouaré. Sau tám năm ở Ligue 1, câu lạc bộ đã xuống hạng hai vào năm 2014. Vì sự xuống hạng này, VAFC đã gặp phải vấn đề tài chính và chứng kiến sự trở lại với công việc kinh doanh của cựu bộ trưởng Jean-Louis Borloo. Ông đã cứu câu lạc bộ tránh khỏi giáng hạng xuống giải hạng tư.